package com.xxzuibang.day8.方法的递规;

/**
 * 思路：
 * 1.先创建迷宫，二维数组表示 int[][] map=new int[8][7];
 * 2.规定map数组的元素值为：0表示可以走，1表示障碍物
 */
public class Test03迷宫问题 {
    public static void main(String[] args) {
        int[][] map=new int[8][7];
        //3.将最上面的一行和最下面的一行全部设置为1
        for (int i = 0; i < 7; i++) {
            map[0][i]=1;
            map[7][i]=1;
        }
        //4.将最右面的一行和最下面的一行全部设置为1
        for (int i = 0; i < 8; i++) {
            map[i][0]=1;
            map[i][6]=1;
        }
        map[3][1]=1;
        map[3][2]=1;
        map[2][2]=1;
        //输出当前的地图
        System.out.println("========当前地图情况=========");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
        //使用findWay给老鼠找路
        Mouse mouse=new Mouse();
        //下右上左
        mouse.findWay(map,1,1);
        System.out.println("\n找路的情况如下：");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }
}

class Mouse{
    /**
     * 使用递归回溯的思想解决老鼠出迷宫问题
     * 1.findWay方法就是专门来找出迷宫的路径
     * 2.如果找到，返回true，否则返回false
     * 3.map是二维数组，表示的是迷宫
     * 4.i，j就是老鼠的位置，初始位置为（1，1）
     * 5.先规定map数组的各个值的含义：0表示可以走，1表示障碍物，2表示可以走，3表示走过但是走不通，是死路
     * 6.当map[6][5]就说明能找到通路，就可以结束了，否则继续找
     * 7.确定找路的策略，下-右-上-左
     */
    public boolean findWay(int[][] map,int i,int j){
        if(map[6][5]==2){//说明已经找到
            return true;
        }else{
            if(map[i][j]==0){
                //假定可以走通
                map[i][j]=2;
                //确定路是否真的可以走通
                if(findWay(map, i+1, j)){//先走下
                    return true;
                }else if(findWay(map, i, j+1)){//右
                    return true;
                }else if(findWay(map, i-1, j)){//上
                    return  true;
                }else if(findWay(map, i, j-1)){//左
                    return  true;
                }else{
                    map[i][j]=3;
                    return false;
                }
            }else{//map[i][j]=1,2,3
                return  false;
            }
        }
    }


}
